package com.sheng.leetcode.year2022.month06.day10;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author liusheng
 * @date 2022/06/10
 *
 * 730. 统计不同回文子序列
 *
 * 给定一个字符串 s，返回 s 中不同的非空「回文子序列」个数 。
 * 通过从 s 中删除 0 个或多个字符来获得子序列。
 * 如果一个字符序列与它反转后的字符序列一致，那么它是「回文字符序列」。
 * 如果有某个 i , 满足 ai != bi ，则两个序列 a1, a2, ... 和 b1, b2, ... 不同。
 * 注意：
 * 结果可能很大，你需要对 109 + 7 取模 。
 *
 * 示例 1：
 *
 * 输入：s = 'bccb'
 * 输出：6
 * 解释：6 个不同的非空回文子字符序列分别为：'b', 'c', 'bb', 'cc', 'bcb', 'bccb'。
 * 注意：'bcb' 虽然出现两次但仅计数一次。
 * 示例 2：
 *
 * 输入：s = 'abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba'
 * 输出：104860361
 * 解释：共有 3104860382 个不同的非空回文子序列，104860361 对 109 + 7 取模后的值。
 *
 * 提示：
 *
 * 1 <= s.length <= 1000
 * s[i] 仅包含 'a', 'b', 'c' 或 'd' 
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/count-different-palindromic-subsequences
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0730 {

    @Test
    public void test01(){
        String s = "bccb";
//        String s = "abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba";
        System.out.println(new Solution().countPalindromicSubsequences(s));
    }

}
//class Solution {
//    public int countPalindromicSubsequences(String s) {
//        return 0;
//    }
//}

//区间 DP
//往长度较少的回文串两端添加字符，可能组成新的长度大的回文串，容易想到「区间 DP」，同时 s 仅由 4 类小写字母组成，也是一个切入点。
//根据区间 DP 的一般思路，定义 f[i][j] 为考虑字符串 s 中的 [i,j] 范围内回文子序列的个数，最终答案为 f[0][n - 1]。
//不失一般性考虑 f[i][j] 该如何转移，通过枚举 abcd 作为回文方案「边缘字符」来进行统计，
//即分别统计各类字符作为「边缘字符」时对 f[i][j] 的贡献，此类统计方式天生不存在重复性问题。
//假设当前枚举到的字符为 k ：
//若 s[i...j] 中没有字符 k，则字符 k 对 f[i][j] 贡献为 0，跳过；
//若 s[i...j] 中存在字符 k，根据字符 k 在范围 s[i...j] 中「最小下标」和「最大下标」进行分情况讨论，
//假设字符 k 在 s[i...j] 中「最靠左」的位置为 l，「最靠右」的位置为 r：
//  当 l = r 时，此时字符 k 对 f[i][j] 的贡献为 1，即 k 本身；
//  当 l = r - 1 时，说明字符 k 中间不存在任何字符，此时字符 k 对 f[i][j] 的贡献为 2，包括 k 和 kk 两种回文方案；
//  其余情况，可根据已算得的「小区间回文方案」进行延伸（两段分别补充位于 l 和 r 的字符 k），
//      得到新的大区间方案，此部分对 f[i][j] 的贡献是 f[l + 1][r - 1]，
//      另外还有 k 和 kk 两种回文方案，因此总的对答案的贡献为 f[l + 1][r - 1] + 2。
//统计 s[i...j] 中各类字符「最靠左」和「最靠右」的位置，
//可通过调整枚举方向来实现：从大到小枚举 i，同时维护 L[s[i]-'a'] = i，即可得到「最靠左」的位置；
//在确定左端点 i 之后，从小到大枚举右端点 j，同时维护 R[s[j]-'a'] = j，即可得到「最靠右」的位置。
//

/**
 * bccb使用
 * 一：
 *      L(i = 3):-1, 3, -1, -1
 *      R(j = 3):-1, 3, -1, -1
 * 二：
 *      L(i = 2):-1,  3, 2, -1
 *      R(j = 2):-1, -1, 2, -1
 *      R(j = 3):-1,  3, 2, -1
 * 三：
 *      L(i = 1):-1,  3, 1, -1
 *      R(j = 1):-1, -1, 1, -1
 *      R(j = 2):-1, -1, 2, -1
 *      R(j = 3):-1,  3, 2, -1
 * 四：
 *      L(i = 0):-1, 0,  1, -1
 *      R(j = 0):-1, 0, -1, -1
 *      R(j = 1):-1, 0,  1, -1
 *      R(j = 2):-1, 0,  2, -1
 *      R(j = 3):-1, 3,  2, -1
 */

class Solution {
    int MOD = (int)1e9+7;
    public int countPalindromicSubsequences(String s) {
        //cs：字符串对应的字符数组
        char[] cs = s.toCharArray();
        //n：字符数组的长度
        int n = cs.length;
        int[][] f = new int[n][n];
        //L数组为左字符a(0)，b(1)，c(2)，d(3)对应的下标，即左边界
        //R数组为确定了左边界的情况下，右边界所对应的下标
        int[] L = new int[4], R = new int[4];
        //将数组L的值填充为-1
        Arrays.fill(L, -1);
        //通过从大到小的枚举方式枚举出 每个字符最靠左的位置
        for (int i = n - 1; i >= 0; i--) {
            //cs[i]为字符数组从后往前取值，减去'a'字符后的下标作为L数组的下标，赋值i
            L[cs[i] - 'a'] = i;
            //将数组R的值填充为-1
            Arrays.fill(R, -1);
            //从i的位置开始包括i本身，从小到大枚举右端点 j
            for (int j = i; j < n; j++) {
                R[cs[j] - 'a'] = j;
                for (int k = 0; k < 4; k++) {
                    //不存在，无贡献，跳过即可
                    if (L[k] == -1 || R[k] == -1) {
                        continue;
                    }
                    //l：坐标表位置，r：右坐标位置
                    int l = L[k], r = R[k];
                    //l == r，此时为单字符a这种情况，对当前字符串的贡献只有其本身
                    if (l == r) {
                        f[i][j] = (f[i][j] + 1) % MOD;
                    } else if (l == r - 1) {
                        //l == r - 1，这种情况，中间的字符串有两个情况，分别为a，或者aa这种情况，贡献为2
                        f[i][j] = (f[i][j] + 2) % MOD;
                    } else {
                        //除上述可能之外，则是中间部分所拥有的可能方案加上这两种回文序列方案后的答案
                        f[i][j] = (f[i][j] + f[l + 1][r - 1] + 2) % MOD;
                    }
                }
            }
        }
        return f[0][n - 1];
    }
}
//
//作者：AC_OIer
//链接：https://leetcode.cn/problems/count-different-palindromic-subsequences/solution/by-ac_oier-lbva/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。


//class Solution {
//    int MOD = (int)1e9 + 7;
//    public int countPalindromicSubsequences(String s) {
//        char[] cs = s.toCharArray();
//        int n = s.length();
//        int[] L = new int[4] , R = new int[4];
//        int[][] f = new int[n][n];
//        Arrays.fill(L , -1);
//        // 通过从大到小的枚举方式枚举出 每个字符最靠左的位置
//        for (int i = n -1 ; i >= 0 ; i--){
//            L[cs[i] - 'a'] = i ;
//            Arrays.fill(R , -1 );
//            // 通过从当前字符最靠左的位置向右一直枚举找到当前字符位于最右侧的位置
//            // 减少枚举次数
//            for (int j = i ; j < n ; j++){
//                R[cs[j] - 'a'] = j;
//
//                for (int k = 0 ; k < 4 ;k++){
//                    // 如果当前字符没有在字符当前 ij 区间中出现过 直接跳过
//                    if (L[k] == -1 || R[k] == -1) continue;
//                    int l = L[k] , r = R[k];
//                    // 如果此时字符串中 i,j 中 最靠左与最靠右的位置相同 则说明当前字符串当中出现的字符只有一个
//                    // 他所能对 当前字符串的贡献只有 其 本身
//                    if (l == r) f[i][j] = (f[i][j] + 1) % MOD;
//                    // 如果此时当前字符的最左侧位置与最右侧位置只隔 1 说明 是两个紧挨着且相同的字符的同时
//                    // 对源贡献为 k 或者 kk 均为回文子字符串
//                    else if (l == r - 1) f[i][j] = (f[i][j] + 2) % MOD ;
//                    else f[i][j] = (f[i][j] + f[l + 1][ r -1] + 2) % MOD ;
//                }
//            }
//        }
//        return f[0][n-1];
//    }
//}
